Renyi Parking Problem

Renyi’s parking problem (or 1D sequential interval packing problem) dates back to 1958, when Renyi studied the following random process:

Consider an interval $I$ of length $x$, and sequentially and randomly pack disjoint unit intervals in $I$ until the remaining space prevents placing any new segment. The expected value of the measure of the covered part of $I$ is $M(x)$, so that the ratio $M(x)/x$ is the expected filling density of the random process. [1]

Renyi himself proves the following continuous recursion for $M(x)$:

$$M(x)= \begin{cases} 0\quad\mathrm{for}\ 0\leq x<1 \\ 1+\frac{2}{x-1}\int_0^{x-1}M(y)dy\quad\mathrm{for}\ x\geq 1 \end{cases}$$

and from this he deduces the asymptotic mean filling density

$$m=\lim_{x\to\infty}M(x)/x=\int_0^\infty\exp[-2\int_0^\infty\frac{1-e^{-y}}{y}dy]\, dx=0.747592\ldots$$

This number is known as Renyi’s Parking Constant.

The first “discretized” version of the problem, namely the expected density derived from sequential packings of non-overlapping neighboring pairs of integer points, i.e., edges or bonds, selected at random on a long segment of a 1D lattice was first given by Page. And [1] gives a better discrete approximation of the above problem.

Similarly but not trivially, we can also obtain an discrete approximation for the case when we have blocks of different types, a.k.a. $A_1$ of length $k_1$ and $A_1$ of length $k_2$. Plus, an elementary C++ code for simulation is given as the following:

#include <iostream>
#include <vector>

using namespace std;

void generator(int park_length, int car_length, int truck_length,
               vector<double> array, double probOfCars,
               double probOfTrucks, int shift_length) {
    double sum1 = 0;
    double sum2 = 0;
    for (int i = 0; i < park_length; ++i) {
        sum1 += array.at(i - car_length + shift_length);
    }
    int upper_limit = park_length - truck_length + car_length +
                        truck_length / 2 - car_length / 2;
    int lower_limit = 1 + truck_length / 2 - car_length / 2;
    if (upper_limit < lower_limit) {
        sum2 = 0;
    } else {
        for (int i = 1; i < park_length; ++i) {
            sum2 += array.at(i - truck_length + shift_length);
        }
    }
    double part1 = 0;
    double part2 = 0;
    if (park_length - truck_length + 1 != 0 && park_length >= car_length) {
        part1 = (double) car_length + 2 * sum1 / (park_length - car_length + 1);
    }
    if (upper_limit > lower_limit &&
        park_length - truck_length + 1 != 0 && park_length <= car_length) {
        part2 = (double) truck_length + 2 * sum1 / (park_length - truck_length + 1);
    }
    array.at(park_length + shift_length) = part1 * probOfCars + part2 * probOfTrucks;
    cout << array.at(park_length + shift_length) / park_length << endl;
}

int main() {

    int parking_length;
    int car1_length;
    int car2_length;
    double prob;
    int confirm;


    while (true) {
        cout << "This is the simulation implemented by C++." <<
         "Please input according to the instructions." << endl;
        cout << "Please enter the length of the parking lot (must be an integer): ";
        cin >> parking_length;
        cout << "Please enter the length of the car 1 (must be an integer): ";
        cin >> car1_length;
        cout << "Please enter the length of the car 2 (must be an integer): ";
        cin >> car2_length;
        cout << "Please enter the probability that the car1 appears: ";
        cin >> prob;
        cout << "The length of the parking lot is " << parking_length << endl;
        cout << "The length of the car1 is " << car1_length << endl;
        cout << "The length of the car2 is " << car2_length << endl;
        cout << "The probability that the car1 appears is " << prob << endl;
        cout << "Please confirm. ( Yes->1 / No->0 ): ";

        cin >> confirm;
        if (confirm != 0) {
            break;
        }
    }

    int shift_length = 2 * parking_length;
    vector<double> array;
    array.resize(parking_length + shift_length + 1);
    cout << array.size() << endl;
    for (int i = shift_length + 1; i < array.size(); ++i) {
        cout << "C " << i - shift_length << " is";
        generator(i - shift_length, car1_length, car2_length,
            array, prob, 1 - prob, shift_length);
    }
    return 0;

}